import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> hash1 = new HashMap<>();//字典中所有单词的出现次数
        for (String word : words) {
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        int len = words[0].length();//每一个单词长度
        int m = words.length;
        for (int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<>();//滑动窗口中单词的出现次数
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                String str = s.substring(right, right + len);
                hash2.put(str, hash2.getOrDefault(str, 0) + 1);
                if (hash2.get(str) <= hash1.getOrDefault(str, 0)) {
                    count++;
                }
                if (right - left + 1 > len * m) {//判断
                    //出窗口加维护count
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                    
                }
                //更新结果
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}


